| A | B | NOT(A · B) | A̅ + B̅ | Verification |
|---|---|---|---|---|
| 0 | 0 | 1 | 1 | ✓ Equal |
| 0 | 0 | 1 | 1 | ✓ Equal |
| 1 | 0 | 1 | 1 | ✓ Equal |
| 1 | 1 | 0 | 0 | ✓ Equal |
What are De Morgan's Theorems?
De Morgan's Theorems are two fundamental rules in Boolean algebra and digital logic, formulated by mathematician Augustus De Morgan. They describe the relationship between AND, OR, and NOT operations, and are essential for simplifying and transforming Boolean expressions in digital circuit design.
Theorem 1 — The NAND Equivalence
Statement: The complement of the product (AND) of two variables equals the sum (OR) of their individual complements.
In plain words: "NOT (A AND B)" is the same as "(NOT A) OR (NOT B)." If it's not the case that both conditions are true, then at least one condition must be false.
Theorem 2 — The NOR Equivalence
Statement: The complement of the sum (OR) of two variables equals the product (AND) of their individual complements.
In plain words: "NOT (A OR B)" is the same as "(NOT A) AND (NOT B)." If neither condition is true, then both conditions must be false.
Why Are the Circuits Equivalent?
Both circuits in each theorem implement the same Boolean function — they map every possible combination of inputs (A, B) to the same output. The truth tables above confirm this: for all four input combinations (00, 01, 10, 11), both the left-side and right-side circuits produce identical outputs. This proves that the circuits are functionally equivalent, regardless of their structural differences.
Practical Significance in Digital Circuit Design
- Gate Conversion: De Morgan's Theorems allow engineers to convert between AND/OR implementations. A NAND gate can replace an OR gate with inverted inputs, and vice versa.
- NAND/NOR Universality: Since NAND and NOR gates are universal (they can implement any Boolean function), De Morgan's Theorems provide the algebraic foundation for this universality.
- Circuit Simplification: Complex Boolean expressions can be simplified by applying these theorems, reducing gate count, cost, and propagation delay.
- Bubble Pushing: In schematic design, De Morgan's Theorems are the basis of "bubble pushing" — a technique to move inversion bubbles through a circuit for easier analysis.
- CMOS Design: In CMOS technology, NAND and NOR gates are more efficient than AND and OR gates. De Morgan's Theorems enable designers to express any logic function using only NAND or only NOR gates.